package P4树形结构;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {

    private class Node {
        public E data;
        public Node left, right;

        public Node(E data) {
            this.data = data;
        }
    }

    private Node root;
    private int size;

    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0 && root == null;
    }

    //添加一个元素进去
    public void add(E data) {
        root = add(root, data);
    }

    //以node为根的子树中插入元素data 并返回新树的根 最好O(logN) 最坏O(N)
    private Node add(Node node, E data) {
        if (node == null) {
            size++;
            return new Node(data);
        } else {
            if (data.compareTo(node.data) < 0) {
                node.left = add(node.left, data);
            } else if (data.compareTo(node.data) > 0) {
                node.right = add(node.right, data);
            }
            return node;
        }
    }

    public boolean contains(E data) {
        return contains(root, data);
    }

    private boolean contains(Node node, E data) { //最好O(logN) 最坏O(N)
        if (node == null) {
            return false;
        } else {
            if (node.data.equals(data)) {
                return true;
            } else if (data.compareTo(node.data) < 0) {
                return contains(node.left, data);
            } else {
                return contains(node.right, data);
            }
        }
    }

    //先序遍历
    public void preOrder() {
        StringBuilder sb = new StringBuilder("先序遍历:[");
        preOrder(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    private void preOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.data);
        sb.append(',');
        sb.append(' ');
        preOrder(node.left, sb);
        preOrder(node.right, sb);
    }

    public void preOrderIteration() {
        StringBuilder sb = new StringBuilder("先序遍历-迭代:[");
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            sb.append(cur.data);
            sb.append(',');
            sb.append(' ');
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    //中序遍历
    public void inOrder() {
        StringBuilder sb = new StringBuilder("中序遍历:[");
        inOrder(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    private void inOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        inOrder(node.left, sb);
        sb.append(node.data);
        sb.append(',');
        sb.append(' ');
        inOrder(node.right, sb);
    }

    public void inOrderIteration() {
        StringBuilder sb = new StringBuilder("中序遍历-迭代:[");
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            sb.append(cur.data);
            sb.append(',');
            sb.append(' ');
            if (cur.right != null) {
                p = cur.right;
                while (p != null) {
                    stack.push(p);
                    p = p.left;
                }
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    //后序遍历
    public void postOrder() {
        StringBuilder sb = new StringBuilder("后序遍历:[");
        postOrder(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    private void postOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        postOrder(node.left, sb);
        postOrder(node.right, sb);
        sb.append(node.data);
        sb.append(',');
        sb.append(' ');
    }

    public void postIteration() {
        StringBuilder sb = new StringBuilder("后序遍历-迭代:[");
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        Node pre = null;
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            Node node = stack.pop();
            if (node.right == null || node.right == pre) {
                sb.append(node.data);
                sb.append(',');
                sb.append(' ');
                pre = node;
            } else {
                stack.push(node);
                p = node.right;
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    //层序遍历
    public void levelOrder() {
        StringBuilder sb = new StringBuilder("层序遍历:[");
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            sb.append(node.data);
            sb.append(',');
            sb.append(' ');
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    public E minmum() {
        if (isEmpty()) {
            throw new IllegalArgumentException("bst is empty");
        }
        return minmum(root).data;
    }

    private Node minmum(Node node) { ////最好O(logN) 最坏O(N)
        if (node.left == null) {
            return node;
        }
        return minmum(node.left);
    }

    public E maxmum() {
        if (isEmpty()) {
            throw new IllegalArgumentException("bst is empty");
        }
        return maxmum(root).data;
    }

    private Node maxmum(Node node) {    ////最好O(logN) 最坏O(N)
        if (node.right == null) {
            return node;
        }
        return maxmum(node.right);
    }

    public E removeMin() {  ////最好O(logN) 最坏O(N)
        E ret = minmum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public E removeMax() {  ////最好O(logN) 最坏O(N)
        E ret = maxmum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public void remove(E data) {
        root = remove(root, data);
    }

    private Node remove(Node node, E data) {    ////最好O(logN) 最坏O(N)
        if (node == null) {
            return null;
        }
        if (data.compareTo(node.data) < 0) {
            node.left = remove(node.left, data);
            return node;
        } else if (data.compareTo(node.data) > 0) {
            node.right = remove(node.right, data);
            return node;
        } else {
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            Node s = minmum(node.right);
            s.right = removeMin(node.right);
            s.left = node.left;
            node.left = node.right = null;
            return s;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new BSTIterator();
    }

    private class BSTIterator implements Iterator<E> {
        private LinkedList<E> list = new LinkedList<>();

        public BSTIterator() {
            LinkedList<Node> stack = new LinkedList<>();
            Node p = root;
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                list.add(cur.data);
                if (cur.right != null) {
                    p = cur.right;
                    while (p != null) {
                        stack.push(p);
                        p = p.left;
                    }
                }
            }
        }

        @Override
        public boolean hasNext() {
            return !list.isEmpty();
        }

        @Override
        public E next() {
            return list.removeFirst();
        }
    }

    //E floor(E e)
    //          返回此 set 中小于等于给定元素的最大元素
    // E ceiling(E e)
    //          返回此 set 中大于等于给定元素的最小元素；
    // E higher(E e)
    //          返回此 set 中严格大于给定元素的最小元素
    //E lower(E e)
    //          返回此 set 中严格小于给定元素的最大元素；
    // 1 2 3 4 5 6 7 8 9


    public E higher(E e) {
        E min = minmum();
        E max = maxmum();
        if (e.compareTo(min) < 0) {
            return min;
        }
        if (e.compareTo(max) > 0) {
            return null;
        }
        inOrderHigher(root, e);
        return cur;
    }

    private E cur;
    private boolean flag = true;

    private void inOrderHigher(Node node, E e) {
        if (node == null) {
            return;
        }
        inOrderHigher(node.left, e);
        if (node.data.compareTo(e) > 0 && flag) {
            cur = node.data;
            flag = false;
        }
        inOrderHigher(node.right, e);
    }

    public E lower(E e) {
        ArrayList<E> list = new ArrayList<>();
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            list.add(cur.data);
            if (cur.right != null) {
                p = cur.right;
                while (p != null) {
                    stack.push(p);
                    p = p.left;
                }
            }
        }
        // 1 2 3 4 6 7 8 9
        if (e.compareTo(list.get(list.size() - 1)) > 0) {
            return list.get(list.size() - 1);
        }
        if (e.compareTo(list.get(0)) < 0) {
            return null;
        }
        int index = binarySearch(list, 0, list.size() - 1, e);
        return list.get(index - 1);
    }

    private int binarySearch(ArrayList<E> list, int low, int high, E key) {
        if (low > high) {
            return low;
        }
        int mid = (high - low) / 2 + low;
        if (list.get(mid).equals(key)) {
            return mid;
        } else if (key.compareTo(list.get(mid)) < 0) {
            return binarySearch(list, low, mid - 1, key);
        } else {
            return binarySearch(list, mid + 1, high, key);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        bst.add(5);
        bst.add(8);
        bst.add(2);
        bst.add(3);
        bst.add(1);
        bst.add(6);
        bst.add(9);
        bst.add(4);
        bst.add(7);
        bst.inOrder();
        bst.inOrderIteration();
        System.out.println(bst.minmum());
        System.out.println(bst.maxmum());
        System.out.println(bst.removeMin());
        System.out.println(bst.removeMax());
        System.out.println(bst.minmum());
        System.out.println(bst.maxmum());
        bst.remove(5);
        bst.inOrder();
//        BinarySearchTree<Integer> bst2 = new BinarySearchTree<>();
//        for (int i = 1; i <= 9; i++) {
//            bst2.add(i);
//        }
//        bst2.inOrderIteration();
//        for (Integer num : bst) {
//            System.out.println(num);
//        }
        System.out.println(bst.lower(5));

        System.out.println(bst.higher(3));
    }

}